package main

func main() {
	//height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	height := []int{4, 2, 0, 3, 2, 5}
	i := trap(height)
	println(i)
}

func trap(height []int) int {
	// dp
	if len(height) == 0 {
		return 0
	}
	numLen := len(height)
	leftMaxArray := make([]int, numLen)
	rightMaxArray := make([]int, numLen)
	leftMaxArray[0] = height[0]
	rightMaxArray[numLen-1] = height[numLen-1]
	for i := 1; i < numLen; i++ {
		currNum := height[i]
		leftMaxArray[i] = maxInt(leftMaxArray[i-1], currNum)
	}
	for i := numLen - 2; i >= 0; i-- {
		currNum := height[i]
		rightMaxArray[i] = maxInt(rightMaxArray[i+1], currNum)
	}
	ans := 0
	for idx, num := range height {
		leftMax := leftMaxArray[idx]
		rightMax := rightMaxArray[idx]
		minMax := minInt(leftMax, rightMax)
		if num < minMax {
			ans += minMax - num
		}
	}
	return ans
}

func trap2(height []int) int {
	// 双指针解法
	numLen := len(height)
	res := 0

	left, right := 0, numLen-1
	leftMax, rightMax := height[left], height[right]

	for left < right {
		if height[left] < height[right] {
			if height[left] < leftMax {
				res += leftMax - height[left]
			} else {
				leftMax = height[left]
			}
			left++
		} else {
			if height[right] < rightMax {
				res += rightMax - height[right]
			} else {
				rightMax = height[right]
			}
			right--
		}
	}

	return res
}

func minInt(num1, num2 int) int {
	if num1 > num2 {
		return num2
	}
	return num1
}

func maxInt(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}

// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
//示例 1：
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//示例 2：
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//提示：
//
//n == height.length
//1 <= n <= 2 * 104
//0 <= height[i] <= 105
